import javax.swing.*;
import java.util.ArrayList;
import java.util.List;

public class DeleteNthNode {
    /*
    * 删除链表的倒数第N个节点
    * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
    * 进阶: 一趟扫描实现
    * */

    /*
     * 注意！！！ 凡是涉及到一个链需要遍历两次的操作，你都先想想能不能用双指针
     * 删除倒数第n个，即目标点和尾部相差n-1步，用双指针！！！！！
     * */

    public static void main(String[] args) {

    }

    // 一趟实现的话，我的想法是遍历一遍获得链表长度，然后依据长度，通过索引实现定位
    public ListNode mySolution(ListNode head, int n){
        List<ListNode> listNodes = new ArrayList<>(30);
        ListNode result = head;
        while (head != null){
            listNodes.add(head);
            head = head.next;
        }
        // 删除第一个
        if(n == listNodes.size()){
            result = result.next;
            return result;
        }
        // 定位删除
        ListNode preNode = listNodes.get(listNodes.size() - n - 1);
        preNode.next = listNodes.get(listNodes.size() - n).next;
        return result;
    }

    // 小子，双指针你是一点也没记住啊！
    /*
    * 注意！！！ 凡是涉及到一个链需要遍历两次的操作，你都先想想能不能用双指针
    * 删除倒数第n个，即目标点和尾部相差n-1步，用双指针！！！！！
    * */
    public ListNode solution(ListNode head, int n){
        // 涉及到删除头，还是要用虚拟头
        ListNode dummyHead = new ListNode(-1, head);
        ListNode fast = dummyHead;
        ListNode slow = dummyHead;
        // 先移动快指针
        for(int i = 1; i <= n; i++){
            fast = fast.next;
        }
        // 再一起移动，直至快指针触底
        while (fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        // 删除节点
        slow.next = slow.next.next;
        return dummyHead.next;
    }

}
